---
title: "抓住那头牛"
created: 2025-11-28
tags:
  - 算法
---

# 抓住那头牛

## 题目 [**抓住那头牛**](https://www.cnblogs.com/littlehb/p/15956835.html)

农夫知道一头牛的位置，想要抓住它。

农夫和牛都位于数轴上，农夫起始位于点 N，牛位于点 K。

农夫有两种移动方式：

从 X 移动到 X−1 或 X+1，每次移动花费一分钟 从 X 移动到 2∗X，每次移动花费一分钟 假设牛没有意识到农夫的行动，站在原地不动。

农夫 **最少** 要花多少时间才能抓住牛？

**输入格式** 共一行，包含两个整数N和K。

**输出格式** 输出一个整数，表示抓到牛所花费的 **最少时间** 。

**数据范围** 0≤N,K≤105

**输入样例**：

```text
5 17
```

**输出样例**：

```text
4
```

## 思路分析

当时看到这题感觉是dp的题 但确实是bfs更好做

又细想了一下区别

好像是一种 每个点都有相同选择的递归模型

这要是放在dfs里面 就是指数型枚举了 然后dp的入门题，跳台阶也是这种类型 指数型枚举进行剪枝，记忆化搜索，然后省去递直接推，逐步优化成dp
好像串起来了

但是有什么区别呢 貌似dfs和dp求的是方案数 而bfs求的是达到某个状态的最少需要的次数 其实dp也能做这件事吧 但是bfs自然适应这种场景的特性
解决起来更为直观且高效

对于这个特定问题，用宽度优先搜索（BFS）通常比动态规划（DP）更高效。原因如下：

1. **直接寻找最短路径**：BFS直接以层级形式扩散搜索，确保找到的第一个解就是最优解，即最短时间。一旦找到目标，搜索即停止。
2. **避免不必要的计算**：BFS在寻找过程中，一旦一个节点被访问，其到起点的最短路径就被确定，不需要重复计算。而DP可能需要计算多条路径到达同一点的情况，尤其是在这个问题的设置中，很多路径可能根本不会被采用。
3. **空间优化**：虽然BFS需要存储当前层的所有节点，但对于这个问题，空间消耗是可控的，特别是考虑到题目给定的数据范围。而DP可能需要一个大数组来存储到每个点的最短时间，尽管在实际操作中这也是可行的。

然而，如果问题变得更加复杂，例如，如果牛也在移动，或者有更复杂的移动规则，动态规划可能就更有优势了，因为它能够更好地处理这种复杂性。动态规划的优势在于它的通用性和对于复杂问题的适应能力，尤其是当问题具有明确的最优子结构和重叠子问题时。

总的来说，对于这个简单的追赶问题，BFS因为其简洁和高效，通常是更好的选择。但DP在处理更复杂或需要找到所有可能解的问题时展现出其强大的能力。在选择算法时，理解问题的本质和算法的特性是关键。

## 代码实现

```cpp
#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

const int N=2e5+10;

int n,k;

int d[N];

bool isVaild(int x){

	return x>=0 && x<=N && d[x]==-1;

}

void bfs(int x){

	queue<int> q;

	memset(d,-1,sizeof d);

	q.push(x);

	d[x]=0;

	while(q.size()){

		int cur=q.front();q.pop();

		if(cur==k){

			cout<<d[k];

			return;

		}

		int choice1=cur+1,choice2=cur-1,choice3=cur*2;

		if(isVaild(choice1)){

			d[choice1]=d[cur]+1;

			q.push(choice1);

		}

		if(isVaild(choice2)){

			d[choice2]=d[cur]+1;

			q.push(choice2);

		}

		if(isVaild(choice3)){

			d[choice3]=d[cur]+1;

			q.push(choice3);

		}

	}

}

int main()

{

	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	cin>>n>>k;

	bfs(n);

	return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[好奇怪的游戏|好奇怪的游戏]] 🏠 [[00-刷题理模型]] ➡️ [[武士风度的牛|武士风度的牛]]